原题链接:[POJ 3422] Kaka's Matrix Travels

闲话

本题是一道比较经典的费用流问题,因此先来介绍一下什么是费用流.

费用流

在给定流网络的前提下,还要引入一个单位流量花费的概念,即每有$1$单位的流量流过就要支付$c$的代价.在满足是最大流的前提下求最大花费或最小花费的模型分别称为最大费用最大流和最小费用最大流.这里一定要注意定义是先满足最大流的性质,然后再谈花费的问题.二分图带权最大匹配可以把每条边的权值看做是单位费用,进而在图上跑最大费用最大流就可以解决问题.

EK增广路算法

在EK求解最大流的基础上,把寻找增广路的BFS换成SPFA即可在求得最大流的前提下,顺便使花费最大/最小.唯一要注意的一点是,在残量网络中反向容量一开始为$0$.但是反向边的单位花费应该设置成相反数.
这一点可能搞混.
那为什么要用SPFA呢,因为维护的残量网络上是存在负权边的,不能用Dijkstra.不过好像也有这种Dijkstra求费用流的方法,过段时间把这里填上.

[POJ 3422] Kaka's Matrix Travels

题目大意:给定一个$n*n$的格子.每个格子里有一个整数,现要求从左上角移动到右下角,每次可以往右边或者下面移动,在经过一个格子之后就会取走里面的整数,之后再经过就没有了,要求找出$k$条路径,使取得的和最大.

思路

费用流模型的一个特点就会带限制的使权值最优.如果没有$k$次路线这个条件,那么整个过程应该就是在图上找一个最长路,这个显然用SPFA就可以做出来.考虑怎么求$k$条路径和建图.

建图

因为这张图上是点权,先拆点,把所有的点都拆成一个入点和一个出点.入点的下标还是原来在矩形中的映射一下,而出点就加$n^2$即可.因此源点即是$1$,而汇点是$2*n^2$.
对于图上每一个点来说,在他自身的入点和出点之间有一条有向边,容量为$1$,费用为$c$.表示过来的第一次可以有$c$的费用.而在这两个点之间再连一条容量为$k-1$,费用为$0$的边,表示之后再来的路径是没有数给你取的.如果要反悔,很简单,你只能走那条费用为$-c$的路,把权值退回来再说,这样就保证了正确性.其次对于往右和往下的边,容量都为$k$,费用为$0$,因为你在图上移动本来就不消耗什么.这里是前一个的出点走到后一个的入点,注意一下关系就行.

是否等价

因为起点的入点和出点之间的容量为$k$,所以往整张图流的容量不会多于$k$.在求解成功得到最大流的前提下,必然是恰好得到了$k$条路径的.其次费用流是保证了最大流再保证费用的,所以恰好找到$k$条路径的条件会被优先满足,因此正确.

代码

注意费用流里的权是单位权,每流一个单位就有一个单位的权,要特别注意这一点,不然答案会算歪.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 200010,INF = 1 << 30;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N],cost[M],st[N],dist[N];
int incf[N],maxflow,res;
inline int link(int x,int y,int k)
{
	return (x - 1) * n + y + k * n * n;
}
void add(int u,int v,int w,int c)
{
	edge[++idx] = v;cap[idx] = w;cost[idx] = c;
	succ[idx] = ver[u];ver[u] = idx; 
	
	edge[++idx] = u;cap[idx] = 0;cost[idx] = -c;
	succ[idx] = ver[v];ver[v] = idx;
}
void update()
{
	int x = t;
	while(x != s)
	{
		int i = pre[x];
		cap[i] -= incf[t];
		cap[i ^ 1] += incf[t];
		x = edge[i ^ 1];
	}
	maxflow += incf[t];
	res += dist[t] * incf[t];
}

bool spfa()
{
	queue<int> q;
	memset(st,0,sizeof st);
	memset(dist,0xcf,sizeof dist);
	q.push(s);st[s] = 1;dist[s] = 0;
	incf[s] = INF;
	while(!q.empty())
	{
		int u = q.front();q.pop();st[u] = 0;
		for(int i = ver[u];i;i = succ[i])
		{
			int j = cap[i];
			if(j)
			{
				int v = edge[i];
				if(dist[v] < dist[u] + cost[i])
				{
					dist[v] = dist[u] + cost[i];
					incf[v] = min(incf[u],cap[i]);
					pre[v] = i;
					if(!st[v])
					{
						st[v] = 1;
						q.push(v);
					}
				}
			}
		}
	}
	if(dist[t] == 0xcfcfcfcf)	return 0;
	return 1;
}

int main()
{
	scanf("%d%d",&n,&m);
	s = 1;t = 2 * n * n;
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
		{
			int c;scanf("%d",&c);
			add(link(i,j,0),link(i,j,1),1,c);
			add(link(i,j,0),link(i,j,1),m - 1,0);
			if(i < n)	add(link(i,j,1),link(i + 1,j,0),m,0);
			if(j < n)	add(link(i,j,1),link(i,j + 1,0),m,0);
		}
	while(spfa())	update();
	printf("%d",res);
    return 0;
}